package Year22_Month07.day02;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class 分割回文串 {
    List<List<String>> resList = new LinkedList<>();//用来保存最后正确的结果
    Deque<String> myList = new LinkedList<>();//用来保存当前的结果
    public List<List<String>> partition(String s) {
        backstracking(0,s);
        return resList;
    }
    public void backstracking(int startIndex,String s){
        //终止条件的判断：如果说后面已经没有地方可以切割了，那么就把当前的子串集合加入结果集中
        if(startIndex > s.length()){
            resList.add(new LinkedList<>(myList));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            //如果说当前的子串是回文串，那么就把当前子串加入到子串集中
            if(isSame(s,startIndex,i)){
                String string = s.substring(startIndex,i+1);
                myList.add(string);
            }else{
                continue;
            }
            //去切割下一个子串
            backstracking(i + 1,s);
            myList.removeLast();
        }
    }
    //判断是否是回文
    public boolean isSame(String s,int start,int end){
        String tmpStr = s.substring(start, end + 1);
        StringBuilder str = new StringBuilder(tmpStr).reverse();
        return tmpStr.equals(str.toString());
    }
}
